package nthUglyNumber

type hp struct {
	value int
	next  *hp
}

func nthUglyNumber(n int) int {
	if n == 1 {
		return 1
	}
	ar := [3]int{2, 3, 5}
	s := 1
	first := &hp{
		value: 1,
	}

	h := &hp{
		next: first,
	}

	for {
		if s == n {
			return h.next.value
		}
		pro := h.Pop()
		s++
		for i := 0; i < 3; i++ {
			h.Push(ar[i] * pro)

		}
	}
}

func (h *hp) Push(v int) {
	if h.next == nil {
		h.next = &hp{
			value: v,
		}
		return
	}
	tmp := h.next
	if v == tmp.value {
		return
	}
	if v < tmp.value {
		new := &hp{
			value: v,
			next:  tmp,
		}
		h = new
		return
	}

	for {
		if tmp.next == nil {
			new := &hp{
				value: v,
			}
			tmp.next = new
			return
		}
		if v == tmp.next.value {
			return
		}
		if v < tmp.next.value {
			new := &hp{
				value: v,
				next:  tmp.next,
			}
			tmp.next = new
			return
		}
		tmp = tmp.next
	}
}

func (h *hp) Pop() int {
	v := h.next.value
	h.next = h.next.next
	return v
}
